WORKING SET
Algoritmo de reemplazo global que utiliza una ventana móvil de tiempo.
Las páginas que no se refieren en este tiempo se quitan del espacio de ejecución.
Para un tamaño T de la ventana (medido en referencias de la memoria), el espacio de ejecución en el tiempo t, es el sistema de las páginas que fueron referenciadas en el intervalo (t - T + 1, t). Una página puede ser substituida cuando no pertenece al espacio de ejecución (No sólo ocurre cuando hay fallos de paginas).
Example:
Dado un programa con 7 páginas virtuales {a,b,...,g} y la secuencia de referencia:
a b a c g a f c g a f d b g
con una ventana de 4 referencias. La siguiente figura muestra el desplazamiento de la ventana donde las referencias contenidas en ella se corresponde con el working Set:
La siguinte tabla muestra el working set después de cada periodo de tiempo:
|
1 |
a |
8 |
acgf |
||
|
2 |
ab |
9 |
acgf |
||
|
3 |
ab |
10 |
acgf |
||
|
4 |
abc |
11 |
acgf |
||
|
5 |
abcg |
12 |
agfd |
||
|
6 |
acg |
13 |
afdb |
||
|
7 |
acgf |
14 |
fdbg |
Una variante del reemplazo básico working set, que sustituye las páginas sólo cuando hay un fallo de página, puede ocurrir cuando:
Si todas las páginas pertenecen al working Set (es decir, han estado alcanzados en las unidades del tiempo de la ventana W antes del fallode página) entonces aumentar el working Set en 1 página.
Si una o más páginas no pertenecen al working Set (es decir, no se han referido a las unidades del tiempo de la ventana W antes del fallo de página) entonces disminuir el working set desechando la página usada recientemente pasada. Si hay más de una página no en el working Set , desechar las 2 páginas que han sido lo menos posible usadas recientemente.